package com.ljy.my_study.lintcode.具有K个不同字符的子串;

import java.util.HashSet;
import java.util.Set;

/** 
* @author James
* @date 2019年2月2日 
*/
public class TestMain {
//	给定字符串S和整数K.
//	计算长度为K且包含K个不同字符的子串数
//
//	样例
//	String: "abcabc"
//	K: 3
//	Answer: 3
//	substrings:  ["abc", "bca", "cab"]
//			
//	String: "abacab"
//	K: 3
//	Answer: 2
//	substrings: ["bac", "cab"]
	public static void main(String[] args) {
		System.out.println(KSubstring("abcabc",3));
	}
	
	public static int KSubstring(String stringIn, int K) {
		int sum=0;
		int len=stringIn.length();
		Set<String> subStringSet=new HashSet<>();
		char[] charArr=new char[K];
		for(int i=0;i<len;i++) {
			if(i+K>len) {
				break;
			}
			boolean flag=true;
			out:for(int j=0;j<K;j++) {
				charArr[j]=stringIn.charAt(i+j);
				in:for(int n=0;n<j;n++) {
					if(charArr[n]==charArr[j]) {
						flag=false;
						break out;
					}
				}
			}
			if(flag) {
				if(!subStringSet.contains(stringIn.substring(i, i+K))) {
					sum++;
					subStringSet.add(stringIn.substring(i, i+K));
				}
			}
		}
		return sum;
	}
}
